package com.aqie.easy.divideAndConquer;

/**
 * 53,最大子序列和
 */
public class MaxSubArray {
    /**
     * 1,暴力方法
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int res = nums[0];
        for (int i = 0; i < nums.length;i++){
            int cur = 0;
            for (int j = i; j < nums.length; j++){
                cur += nums[j];
                res = Math.max(res, cur);
            }
        }
        return res;
    }

    /**
     * 2,动态规划 O(n)
     * 如果此时的子序列之和小于 0 的话，那么从当前位置开始的新子序列一定比保留原来的子序列的和更大。
     * 递推公式：dp[i] = Math.max(dp[i - 1] + nums[i], nums[i])
     * @param nums
     */
    public int maxSubArray2(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int res = nums[0];
        int cur = nums[0];
        for(int i = 1; i < nums.length; i ++) {
            if(cur <= 0) {
                cur = nums[i];
            } else {
                cur += nums[i];
            }

            res = Math.max(cur, res);
        }

        return res;

    }

    /**
     * 3. 分治 O(nlogn)
     * 左部分找最大连续子序列和
     * 右部分找最大连续子序列和
     * 跨过 mid 的最大连续子序列和
     * @param nums
     * @return
     */
    public int maxSubArray3(int[] nums) {
        return find(nums, 0, nums.length - 1);
    }

    private int find(int[] nums, int start, int end) {
        if(start == end) {
            return nums[start];
        }

        if(start > end) {
            return Integer.MIN_VALUE;
        }

        int mid = start + (end - start) / 2;
        int leftMax = find(nums, start, mid - 1);
        int rightMax = find(nums, mid + 1, end);

        int ml = 0;
        for(int i = mid - 1, sum = 0; i >= start; i --) {
            sum += nums[i];
            ml = Math.max(ml, sum);
        }

        int mr = 0;
        for(int i = mid + 1, sum = 0; i <= end; i ++) {
            sum += nums[i];
            mr = Math.max(mr, sum);
        }

        return Math.max(Math.max(leftMax, rightMax), ml + mr + nums[mid]);
    }


    public static void main(String[] args) {
        int[] arr = {-2,1,-3,4,-1,2,1,-5,4};
    }
}
